1783. Минимальный лексикографически циклический сдвиг

Перестановкой порядка n называется последовательность из попарно различных целых положительных чисел p₁, p₂, ..., p_n, где каждое 1 ≤ p_i ≤ n. Будем говорить, что перестановка q₁, q₂, ..., q_n лексикографически меньше перестановки p₁, p₂, ..., p_n, если существует такое i, что q_i < p_i, а для любого j < i p_j = q_j.

Циклическим сдвигом на k перестановки p₁, p₂, ..., p_n называется последовательность p_k+1, p_k+2, ..., p_n, p₁, ..., p_k. Отметим, что любой циклический сдвиг перестановки также является перестановкой.

Найдите наименьший лексикографически циклический сдвиг заданной перестановки.

Вход. Первая строка содержит порядок n (1 ≤ n ≤ 10⁵) заданной перестановки. Вторая строка содержит числа p₁, p₂, ..., p_n.

Выход. Выведите перестановку, являющуюся наименьшим лексикографически циклическим сдвигом перестановки, заданной на входе. Используйте такой же формат, в каком перестановка задана во второй строке входных данных.

Пример входа	Пример выхода
3 3 2 1	3 3 2 1

РЕШЕНИЕ

массив

Анализ алгоритма

Входная перестановка содержит числа от 1 до n в некотором порядке. Лексически наименьшим цмклическим сдвигом будет перестановка, которая начинается с 1. Пусть i – позиция 1 в исходной перестановке. Тогда выводим:

· элементы перестановки с позиции i до конца;

· элементы перестановки с начала до позиции i – 1;

Реализация алгоритма

Входную перестановку храним в массиве p.

int p[100000];

Читаем входные данные.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &p[i]);

Ищем позицию i, в которой находится 1.

for (i = 0; i < n; i++)

if (p[i] == 1)

{

Выводим числа с позиции i до конца перестановки.

for (j = i; j < n; j++)

printf("%d ", p[j]);

Выводим числа с начала перестановки до позиции i – 1.

for (j = 0; j < i; j++)

printf("%d ", p[j]);

return 0;

}